{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check If a Number Is Majority Element in a Sorted Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isMajorityElement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #检查一个数是否在数组中占绝大多数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出一个按 <strong>非递减</strong> 顺序排列的数组 <code>nums</code>，和一个目标数值 <code>target</code>。假如数组 <code>nums</code> 中绝大多数元素的数值都等于 <code>target</code>，则返回 <code>True</code>，否则请返回 <code>False</code>。</p>\n",
    "\n",
    "<p>所谓占绝大多数，是指在长度为 <code>N</code> 的数组中出现必须<strong> 超过 <code>N/2</code></strong> <strong>次</strong>。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,4,5,5,5,5,5,6,6], target = 5\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>\n",
    "数字 5 出现了 5 次，而数组的长度为 9。\n",
    "所以，5 在数组中占绝大多数，因为 5 次 > 9/2。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [10,100,101,101], target = 101\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>\n",
    "数字 101 出现了 2 次，而数组的长度是 4。\n",
    "所以，101 <strong>不是 </strong>数组占绝大多数的元素，因为 2 次 = 4/2。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 1000</code></li>\n",
    "\t<li><code>1 <= nums[i] <= 10^9</code></li>\n",
    "\t<li><code>1 <= target <= 10^9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-a-number-is-majority-element-in-a-sorted-array](https://leetcode.cn/problems/check-if-a-number-is-majority-element-in-a-sorted-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-a-number-is-majority-element-in-a-sorted-array](https://leetcode.cn/problems/check-if-a-number-is-majority-element-in-a-sorted-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,4,5,5,5,5,5,6,6]\\n5', '[10,100,101,101]\\n101']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], t: int) -> bool:\n",
    "        return bisect_right(nums, t) - bisect_left(nums, t) > len(nums) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        n = len(nums) // 2\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            if num == target:\n",
    "                cnt += 1\n",
    "        return cnt > n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        # 双指针\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left < right:\n",
    "            if nums[left] != target:\n",
    "                left += 1\n",
    "            elif nums[right] != target:\n",
    "                right -=1 \n",
    "            else:\n",
    "                return (right - left + 1) > len(nums) // 2\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        def search(nums, target):\n",
    "            l, r = 0, len(nums)-1\n",
    "            while l < r:\n",
    "                m = (l+r)//2\n",
    "                if nums[m] == target:\n",
    "                    if m == 0: return m\n",
    "                    if nums[m-1] < target:\n",
    "                        return m\n",
    "                    else:\n",
    "                        r = m\n",
    "                elif nums[m] < target:\n",
    "                    l = m+1\n",
    "                else:\n",
    "                    r = m\n",
    "\n",
    "            return -1\n",
    "\n",
    "        l = search(nums, target)\n",
    "        return l>=0 and l+len(nums)//2 < len(nums) and nums[l+len(nums)//2]==target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        l = len(nums)\n",
    "        dic = collections.Counter(nums)\n",
    "        return True if l/2 < dic[target] else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        index_1 = bisect.bisect_left(nums, target)\n",
    "        index_2 = bisect.bisect_right(nums, target) - 1\n",
    "\n",
    "        if (index_2 - index_1 + 1) > len(nums)/2:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        from collections import Counter\n",
    "        return True if [k for k,v in Counter(nums).items() if v > len(nums)/2 and k==target] else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        # target = nums[len(nums)//2]\n",
    "        l = bisect.bisect_left(nums, target)\n",
    "        r = bisect.bisect_right(nums, target)\n",
    "        if r - l > len(nums)//2:\n",
    "            return True\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        n=len(nums)\n",
    "        m=nums.count(target)\n",
    "        return m*2>n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        vote = 0\n",
    "        for num in nums:\n",
    "            if vote == 0:\n",
    "                x = num\n",
    "            vote += 1 if num == x else -1\n",
    "        \n",
    "        count = 0\n",
    "        for num in nums:\n",
    "            if num == x: \n",
    "                count += 1\n",
    "        return True if x == target and count > len(nums) // 2 else False \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        n = len(nums)\n",
    "        return (bisect_right(nums, target) - bisect_left(nums, target)) > n // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if target < nums[0] or target > nums[-1]:\n",
    "            return False\n",
    "        import bisect\n",
    "\n",
    "        left = bisect.bisect_left(nums, target)\n",
    "        right = bisect.bisect_right(nums, target)\n",
    "        if right-left > n/2:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "\n",
    "        c = collections.Counter(nums)\n",
    "        return c[target] * 2 > len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        return nums.count(target) > len(nums) / 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        count = 0\n",
    "        for i in nums:\n",
    "            if i == target:\n",
    "                count+=1\n",
    "        if count > len(nums)/2:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "\n",
    "        c = collections.Counter(nums)\n",
    "        return c[target] * 2 > len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        left, right = 0, len(nums) - 1\n",
    "        mid = (left + right) // 2\n",
    "        if nums[mid] != target:\n",
    "            return False\n",
    "        while left <= mid and right >= mid:\n",
    "            if nums[left] != target:\n",
    "                left += 1\n",
    "            elif nums[right] != target:\n",
    "                right -= 1\n",
    "            else:\n",
    "                break\n",
    "        return (right - left + 1) > len(nums) / 2\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        majority = len(nums) / 2\n",
    "\n",
    "        count = collections.Counter(nums)\n",
    "\n",
    "        for key, val in count.items():\n",
    "            if key == target and val > majority:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "\n",
    "        def find_first():\n",
    "            start, end = 0, len(nums) - 1\n",
    "\n",
    "            while start < end - 1:\n",
    "                mid = int(start + (end - start) / 2)\n",
    "\n",
    "                if nums[mid] < target:\n",
    "                    start = mid\n",
    "                else:\n",
    "                    end = mid\n",
    "            \n",
    "            return start if nums[start] == target else end\n",
    "\n",
    "        def find_last():\n",
    "            start, end = 0, len(nums) - 1\n",
    "\n",
    "            while start < end - 1:\n",
    "                mid = int(start + (end - start) / 2)\n",
    "\n",
    "                if nums[mid] <= target:\n",
    "                    start = mid\n",
    "                else:\n",
    "                    end = mid\n",
    "            \n",
    "            return end if nums[end] == target else start\n",
    "\n",
    "        first_idx = find_first()\n",
    "        last_idx = find_last()\n",
    "\n",
    "        if nums[first_idx] != target or nums[last_idx] != target:\n",
    "            return False\n",
    "        \n",
    "        return (last_idx - first_idx + 1) > int(len(nums) / 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: [int], target: int) -> bool:\n",
    "        left_bound = self.left_bound(nums, 0, len(nums) - 1, target)\n",
    "        right_bound = self.right_bound(nums, 0, len(nums) - 1, target)\n",
    "        if left_bound == -1 and right_bound == -1:\n",
    "            return False\n",
    "        elif nums[right_bound]!=target:\n",
    "            return False\n",
    "        if left_bound == -1:\n",
    "            left_bound = 0\n",
    "        if right_bound == -1:\n",
    "            right_bound = len(nums) - 1\n",
    "        return right_bound - left_bound + 1 > len(nums) // 2\n",
    "\n",
    "    def left_bound(self, nums: [int], left: int, right: int, target: int):\n",
    "        res = -1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if nums[mid] >= target:\n",
    "                res = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return res\n",
    "\n",
    "    def right_bound(self, nums: [int], left: int, right: int, target: int):\n",
    "        res = -1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if nums[mid] <= target:\n",
    "                res = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if target < nums[0] or target > nums[-1]:\n",
    "            return False\n",
    "        import bisect\n",
    "\n",
    "        left = bisect.bisect_left(nums, target)\n",
    "        right = bisect.bisect_right(nums, target)\n",
    "        if right-left > n/2:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        left = self.find_left_boundary(nums, target)\n",
    "        right = self.find_right_boundary(nums, target)\n",
    "        if left == -1 or right == -1:\n",
    "            return False\n",
    "        if right - left + 1 > len(nums) / 2:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def find_left_boundary(self, nums, target):\n",
    "        l, r = 0, len(nums) - 1\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if nums[mid] < target:\n",
    "                l = mid + 1\n",
    "            elif nums[mid] >= target:\n",
    "                r = mid - 1\n",
    "        if l == len(nums):\n",
    "            return -1\n",
    "        return l if nums[l] == target else -1\n",
    "    \n",
    "    def find_right_boundary(self, nums, target):\n",
    "        l, r = 0, len(nums) - 1\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if nums[mid] <= target:\n",
    "                l = mid + 1\n",
    "            elif nums[mid] > target:\n",
    "                r = mid - 1\n",
    "        if l - 1 < 0 or l - 1 >= len(nums):\n",
    "            return -1\n",
    "        return l - 1 if nums[l - 1] == target else -1\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        d = defaultdict(int)\n",
    "        for x in nums:\n",
    "            d[x]+=1\n",
    "        n = len(nums)\n",
    "        return d[target]>n/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        return nums.count(target) > len(nums)/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        count = 0\n",
    "        for i in nums:\n",
    "            if i == target:\n",
    "                count += 1\n",
    "        if count > len(nums)/2:\n",
    "            return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        cnt = 0\n",
    "        cc = len(nums) / 2\n",
    "        for n in nums:\n",
    "            if n == target:\n",
    "                cnt += 1\n",
    "            if cnt > cc:\n",
    "                return True\n",
    "            if cnt > 0 and n != target:\n",
    "                return False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        if nums[len(nums)//2]!=target:\n",
    "            return False\n",
    "        count=0\n",
    "        for num in nums:\n",
    "            if num==target:\n",
    "                count+=1\n",
    "        return count>len(nums)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        min_maj = len(nums)//2 + 1\n",
    "        i = 0\n",
    "        j = min_maj-1\n",
    "        while j < len(nums):\n",
    "            if nums[i] == nums[j] and nums[j] == target:\n",
    "                return True\n",
    "            i += 1\n",
    "            j += 1\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        count = 0\n",
    "        for num in nums:\n",
    "            if num == target:\n",
    "                count += 1\n",
    "        return True if count > len(nums)// 2 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        return nums.count(target)>len(nums)/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        return True if nums.count(target) > len(nums) // 2 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        left = self.binarySearch_left(nums,target)\n",
    "        if left + len(nums)//2 >= len(nums):\n",
    "            return False\n",
    "        else:\n",
    "            return nums[left + len(nums)//2]==target\n",
    "    \n",
    "\n",
    "    def binarySearch_left(self,nums: List[int], target: int) -> int:\n",
    "        l,r = 0, len(nums)-1\n",
    "        while l<r:\n",
    "            mid = (l+r) >>1\n",
    "            if nums[mid] >= target:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid+1\n",
    "        \n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if target < nums[0] or target > nums[-1]:\n",
    "            return False\n",
    "        import bisect\n",
    "\n",
    "        left = bisect.bisect_left(nums, target)\n",
    "        right = bisect.bisect_right(nums, target)\n",
    "        if right-left > n/2:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        vote = 0\n",
    "        for num in nums:\n",
    "            if vote == 0:\n",
    "                x = num\n",
    "            vote += 1 if num == x else -1\n",
    "        \n",
    "        # 验证 x 是否为众数\n",
    "        count = 0\n",
    "        for num in nums:\n",
    "            if num == x: \n",
    "                count += 1\n",
    "        return True if x == target and count > len(nums) // 2 else False \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        return True if nums.count(target) > len(nums) // 2 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        length = len(nums)\n",
    "        flag = False\n",
    "        count = 0\n",
    "        for i in range(0,length):\n",
    "            if nums[i] == target:\n",
    "                count += 1\n",
    "                flag = True\n",
    "            else:\n",
    "                if(flag):\n",
    "                    break\n",
    "        return count > length / 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        n = len(nums)\n",
    "        left, right = 0, n-1\n",
    "        def erfen(left, right, target):\n",
    "            while left <= right:\n",
    "                mid = (left + right)//2\n",
    "                if nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return left\n",
    "        index1 = erfen(left, right, target)\n",
    "        index2 = erfen(left, right, target+1)\n",
    "        print(index1, index2)\n",
    "        return (index2-index1) > n/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            if num == target:\n",
    "                cnt+=1\n",
    "        return cnt > len(nums)/2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\r\n",
    "        n = len(nums)\r\n",
    "        #L = bisect.bisect_left(nums, target)\r\n",
    "        #R = bisect.bisect_right(nums, target)\r\n",
    "        L = self.binary_search_left(nums, target)\r\n",
    "        R = self.binary_search_right(nums, target)\r\n",
    "        cur_len = R - L\r\n",
    "        return cur_len > n // 2\r\n",
    "    \r\n",
    "    def binary_search_left(self, nums: List[int], target: int) -> int:\r\n",
    "        L, R = 0, len(nums)\r\n",
    "        while L < R:\r\n",
    "            mid = (L + R) >> 1\r\n",
    "            if nums[mid] >= target: #寻找符合条件最左端\r\n",
    "                R = mid\r\n",
    "            else:\r\n",
    "                L = mid + 1\r\n",
    "        return L\r\n",
    "\r\n",
    "    def binary_search_right(self, nums: List[int], target: int) -> int:\r\n",
    "        L, R = 0, len(nums)\r\n",
    "        while L < R:\r\n",
    "            mid = (L + R) >> 1\r\n",
    "            if nums[mid] > target:  #寻找符合提交的最左端\r\n",
    "                R = mid\r\n",
    "            else:\r\n",
    "                L = mid + 1\r\n",
    "        return L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if target < nums[0] or target > nums[-1]:\n",
    "            return False\n",
    "        import bisect\n",
    "\n",
    "        left = bisect.bisect_left(nums, target)\n",
    "        right = bisect.bisect_right(nums, target)\n",
    "        print(left, right)\n",
    "        if right-left > n/2:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        freq = {}\n",
    "        for val in nums:\n",
    "            if val in freq:\n",
    "                freq[val] += 1\n",
    "            else:\n",
    "                freq[val] = 1\n",
    "        for item in freq:\n",
    "            if freq[item] > len(nums)/2:\n",
    "                if item == target:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        def search(nums, target):\n",
    "            l, r = 0, len(nums)-1\n",
    "            while l < r:\n",
    "                m = (l+r)//2\n",
    "                if nums[m] == target:\n",
    "                    if m == 0: return m\n",
    "                    if nums[m-1] < target:\n",
    "                        return m\n",
    "                    else:\n",
    "                        r = m\n",
    "                elif nums[m] < target:\n",
    "                    l = m+1\n",
    "                else:\n",
    "                    r = m\n",
    "\n",
    "            return -1\n",
    "\n",
    "        l = search(nums, target)\n",
    "        print(l)\n",
    "        return l>=0 and l+len(nums)//2 < len(nums) and nums[l+len(nums)//2]==target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        return nums.count(target) > len(nums) / 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        return self.answer_1(nums, target)\n",
    "\n",
    "    def answer_1(self, nums, target):\n",
    "        cnt = 0\n",
    "\n",
    "        for num in nums:\n",
    "            if num == target:\n",
    "                cnt += 1\n",
    "\n",
    "        return cnt > len(nums) // 2\n",
    "\n",
    "    def answer_2(self, nums, target):\n",
    "\n",
    "        def _search_left():\n",
    "            start = 0\n",
    "            end = len(nums) - 1\n",
    "\n",
    "            while start <= end:\n",
    "                mid = (start + end) // 2\n",
    "                cmp_target = nums[mid]\n",
    "                if cmp_target == target:\n",
    "                    end = mid - 1\n",
    "                elif cmp_target < target:\n",
    "                    start = mid + 1\n",
    "                elif cmp_target > target:\n",
    "                    end = mid - 1\n",
    "            return start\n",
    "\n",
    "        def _search_right():\n",
    "            start = 0\n",
    "            end = len(nums) - 1\n",
    "\n",
    "            while start <= end:\n",
    "                mid = (start + end) // 2\n",
    "                cmp_target = nums[mid]\n",
    "                if cmp_target == target:\n",
    "                    start = mid + 1\n",
    "                elif cmp_target < target:\n",
    "                    start = mid + 1\n",
    "                elif cmp_target > target:\n",
    "                    end = mid - 1\n",
    "            return end\n",
    "\n",
    "        left = _search_left()\n",
    "        right = _search_right()\n",
    "\n",
    "        return (right - left + 2) > len(nums) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        count = 0\n",
    "        for num in nums:\n",
    "            if num == target:\n",
    "                count += 1\n",
    "        return count * 2 > len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        return self.answer_1(nums, target)\n",
    "\n",
    "    def answer_1(self, nums, target):\n",
    "        cnt = 0\n",
    "\n",
    "        for num in nums:\n",
    "            if num == target:\n",
    "                cnt += 1\n",
    "\n",
    "        return cnt > len(nums) // 2\n",
    "\n",
    "    def answer_2(self, nums, target):\n",
    "\n",
    "        def _search_left():\n",
    "            start = 0\n",
    "            end = len(nums) - 1\n",
    "\n",
    "            while start <= end:\n",
    "                mid = (start + end) // 2\n",
    "                cmp_target = nums[mid]\n",
    "                if cmp_target == target:\n",
    "                    end = mid - 1\n",
    "                elif cmp_target < target:\n",
    "                    start = mid + 1\n",
    "                elif cmp_target > target:\n",
    "                    end = mid - 1\n",
    "            return end\n",
    "\n",
    "        def _search_right():\n",
    "            start = 0\n",
    "            end = len(nums) - 1\n",
    "\n",
    "            while start <= end:\n",
    "                mid = (start + end) // 2\n",
    "                cmp_target = nums[mid]\n",
    "                if cmp_target == target:\n",
    "                    start = mid + 1\n",
    "                elif cmp_target < target:\n",
    "                    start = mid + 1\n",
    "                elif cmp_target > target:\n",
    "                    end = mid - 1\n",
    "            return start\n",
    "\n",
    "        left = _search_left()\n",
    "        right = _search_right()\n",
    "\n",
    "        return (right - left + 2) > len(nums) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        n=len(nums)\n",
    "        idx=bisect.bisect_left(nums,target)\n",
    "        if  n-idx<=n//2  or nums[idx]!=target :\n",
    "            return False\n",
    "        if nums[idx+n//2]==target:\n",
    "            return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        num_size = len(nums)\n",
    "        enough_size = num_size // 2 + 1\n",
    "\n",
    "        for index, num in enumerate(nums):\n",
    "            if num == target:\n",
    "                return (index + enough_size - 1 < len(nums)) and nums[index + enough_size - 1] == target\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            if nums[mid]>=target:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        leftside = left \n",
    "        left, right = 0, len(nums)-1\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            if nums[mid]<=target:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        rightside = right\n",
    "        print(leftside,rightside)\n",
    "        return rightside-leftside+1 > len(nums)/2\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "\n",
    "        def searchLeft(nums, target):\n",
    "            left, right = 0, len(nums) - 1\n",
    "            while left <= right: #[right+1, right]\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums[mid] == target:\n",
    "                    right = mid - 1\n",
    "                elif nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] > target:\n",
    "                    right = mid - 1\n",
    "            return right + 1\n",
    "\n",
    "        \n",
    "        def searchRight(nums, target):\n",
    "            left, right = 0, len(nums) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums[mid] == target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] > target:\n",
    "                    right = mid - 1\n",
    "            return left - 1\n",
    "\n",
    "\n",
    "        left_end = searchLeft(nums, target)\n",
    "        right_end = searchRight(nums, target)\n",
    "        print(left_end, right_end)\n",
    "        return (right_end - left_end + 1) > (len(nums) / 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "\n",
    "        def searchLeft(nums, target):\n",
    "            left, right = 0, len(nums) - 1\n",
    "            while left <= right: #[right+1, right]\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums[mid] == target:\n",
    "                    right = mid - 1\n",
    "                elif nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] > target:\n",
    "                    right = mid - 1\n",
    "            return right + 1\n",
    "\n",
    "        \n",
    "        def searchRight(nums, target):\n",
    "            left, right = 0, len(nums) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums[mid] == target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] > target:\n",
    "                    right = mid - 1\n",
    "            return left - 1\n",
    "\n",
    "\n",
    "        left_end = searchLeft(nums, target)\n",
    "        right_end = searchRight(nums, target)\n",
    "        print(left_end, right_end)\n",
    "        return (right_end - left_end + 1) > (len(nums) / 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "\n",
    "        def searchLeft(nums, target):\n",
    "            left, right = 0, len(nums) - 1\n",
    "            while left <= right: #[right+1, right]\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums[mid] == target:\n",
    "                    right = mid - 1\n",
    "                elif nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] > target:\n",
    "                    right = mid - 1\n",
    "            return right + 1\n",
    "\n",
    "        \n",
    "        def searchRight(nums, target):\n",
    "            left, right = 0, len(nums) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums[mid] == target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] > target:\n",
    "                    right = mid - 1\n",
    "            return left - 1\n",
    "\n",
    "\n",
    "        left_end = searchLeft(nums, target)\n",
    "        right_end = searchRight(nums, target)\n",
    "        print(left_end, right_end)\n",
    "        return (right_end - left_end + 1) > (len(nums) / 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "        # 使用二分查找找到目标元素的第一个位置\n",
    "        def first_occurrence(nums: List[int], target: int) -> int:\n",
    "            left, right = 0, len(nums) - 1\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left if nums[left] == target else -1\n",
    "        \n",
    "        # 使用二分查找找到目标元素的最后一个位置\n",
    "        def last_occurrence(nums: List[int], target: int) -> int:\n",
    "            left, right = 0, len(nums) - 1\n",
    "            while left < right:\n",
    "                mid = left + (right - left + 1) // 2\n",
    "                if nums[mid] > target:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid\n",
    "            return left if nums[left] == target else -1\n",
    "\n",
    "        first_pos = first_occurrence(nums, target)\n",
    "        if first_pos == -1:\n",
    "            return False\n",
    "        last_pos = last_occurrence(nums, target)\n",
    "        \n",
    "        # 检查目标元素的出现次数是否超过 N/2\n",
    "        return (last_pos - first_pos + 1) > len(nums) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "\n",
    "        def searchLeft(nums, target):\n",
    "            left, right = 0, len(nums) - 1\n",
    "            while left <= right: #[right+1, right]\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums[mid] == target:\n",
    "                    right = mid - 1\n",
    "                elif nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] > target:\n",
    "                    right = mid - 1\n",
    "            return right + 1\n",
    "\n",
    "        \n",
    "        def searchRight(nums, target):\n",
    "            left, right = 0, len(nums) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums[mid] == target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] > target:\n",
    "                    right = mid - 1\n",
    "            return left - 1\n",
    "\n",
    "\n",
    "        left_end = searchLeft(nums, target)\n",
    "        right_end = searchRight(nums, target)\n",
    "        print(left_end, right_end)\n",
    "        return (right_end - left_end + 1) > (len(nums) / 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMajorityElement(self, nums: List[int], target: int) -> bool:\n",
    "\n",
    "        def searchLeft(nums, target):\n",
    "            left, right = 0, len(nums) - 1\n",
    "            while left <= right: #[right+1, right]\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums[mid] == target:\n",
    "                    right = mid - 1\n",
    "                elif nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] > target:\n",
    "                    right = mid - 1\n",
    "            return right + 1\n",
    "\n",
    "        \n",
    "        def searchRight(nums, target):\n",
    "            left, right = 0, len(nums) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums[mid] == target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] > target:\n",
    "                    right = mid - 1\n",
    "            return left - 1\n",
    "\n",
    "\n",
    "        left_end = searchLeft(nums, target)\n",
    "        right_end = searchRight(nums, target)\n",
    "        print(left_end, right_end)\n",
    "        return (right_end - left_end + 1) > (len(nums) / 2)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
